package com.ifish.leetcode.problem.algorithm;

import com.ifish.leetcode.problem.BaseLeetCodeProblem;

/**
 * Created by iFish on 17/7/11.
 */

// Given a roman numeral, convert it to an integer.
// Input is guaranteed to be within the range from 1 to 3999.

public class _0013 extends BaseLeetCodeProblem {
    @Override
    public String title() {
        return "Roman to Integer";
    }

    @Override
    public void run() {
        super.run();

        printResult(romanToInt("MMMDLXXXVI"));
    }

    // 先添加所有，再减去多余（这居然会超时？。。）
    private int romanToInt2(String s) {
        int r = 0;
        int minus = 0;
        char lastChar = '_';
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            r += valueOfChar(c);
            minus += minusNum(lastChar, c);
            lastChar = c;
        }
        return r - minus;
    }

    // 笨办法，顺着找数字区间
    public int romanToInt(String s) {
        int r = 0;
        int len = s.length();
        if (len == 1) return valueOfChar(s.charAt(0));

        char lastc = '_';
        boolean needCheckMinus = false;
        boolean needMinus = false;
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (needCheckMinus) { // 上一个字符可能被本字符减去
                if (needMinus(lastc, c)) {
                    needMinus = true; // 标记需要-
                } else {
                    r += valueOfChar(lastc); // 不会被减，直接+
                }
                needCheckMinus = false;
            }
            if (needMinus) {
                r += (valueOfChar(c) - valueOfChar(lastc)); // 加上减去后的值
                needMinus = false;
            } else if (needCheckMinus(c) && i < len - 1) {
                needCheckMinus = true; // 重新计算数字区间，需要检查减法
            } else {
                r += valueOfChar(c); // 重新计算数字区间，不需要检查减法
            }
            lastc = c;
        }
        return r;
    }

    private int valueOfChar(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }

    private boolean needCheckMinus(char c) {
        return c == 'I' || c == 'X' || c == 'C';
    }

    private boolean needMinus(char left, char right) {
        return (left == 'I' && (right == 'V' || right == 'X')) ||
                (left == 'X' && (right == 'L' ||right == 'C')) ||
                (left == 'C' && (right == 'D' || right == 'M'));
    }

    private int minusNum(char left, char right) {
        if (left == 'I' && (right == 'V' || right == 'X')) {
            return 2;
        } else if (left == 'X' && (right == 'L' ||right == 'C')) {
            return 20;
        } else if (left == 'C' && (right == 'D' || right == 'M')) {
            return 200;
        }
        return 0;
    }
}
